<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>Title</title>
  </head>
  <body>
    <script>
      /*给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

    路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

     

    示例 1：



    输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
    输出：3
    解释：和等于 8 的路径有 3 条，如图所示。
    示例 2：

    输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    输出：3
     
    提示:

    二叉树的节点个数的范围是 [0,1000]
    -109 <= Node.val <= 109 
    -1000 <= targetSum <= 1000 
    通过次数89,625提交次数158,173

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/path-sum-iii
               8
              / \
             3   2
            / \   \
           8   6   9
            */
      const tree = {
        val: 8,
        left: {
          val: 3,
          left: { val: 8, left: null, right: null },
          right: { val: 6, left: null, right: null },
        },
        right: {
          val: 2,
          left: null,
          right: { val: 9, left: null, right: null },
        },
      };

      //https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-kcb0/

      let count = 0;
      let allPath = [];

      // 双重递归
      var pathSum = function (root, targetSum) {
        if (!root) return 0;
        dfs(root, targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return count;
      };

      var dfs = function (target, targetSum) {
        if (!target) return;

        targetSum -= target.val;
        if (targetSum === 0) {
          count++;
        }
        dfs(target.left, targetSum);
        dfs(target.right, targetSum);
      };

      console.log(pathSum(tree, 9));
      console.log(count);
    </script>
  </body>
</html>
